Conventional methods of coding segmented pictures—or partitions—are usually considered as rather expensive in terms of amount of bits, e.g. an average value of 1,3 bit per pixel of contour with the so-called chain code technique. Lossy shape coding techniques have therefore been proposed, but losses in shape information often result in an unacceptable degradation of the subjective quality of the image displayed on the basis of the decoded picture.
Quasi-lossless shape coding techniques (and therefore, by extension, quasi-lossless partition coding techniques) have then been proposed. For instance, the so-called multiple grid chain code approach (MGCC), described in the document “Multiple grid chain coding of binary shapes”, by P. Nunes, F. Ferreira and F. Marqués, Proceedings of International Conference on Image Processing, vol. III, pp. 114–117, Oct. 26–29, 1997, Santa Barbara, Calif., USA, allows to efficiently encode binary shape information of video objects in the context of object-based video coding schemes. Said approach also allows general partition coding, while introducing very few and controlled losses, only restricted to isolated picture elements (pixels) belonging to the boundaries of the regions of each partition.
This conventional MGCC approach relies on a contour representation of the partition. As shown in FIG. 1 that depicts a small general partition of size N×M with for example three regions to which respective labels (in the present case, represented by the grey, black and white circles) are associated, any pixel has four different contour elements associated. FIG. 2 shows the same partition as depicted in FIG. 1, but with the indication of the specific contour elements that define the changes between every pair of neighbour pixels that do not belong to the same region. FIG. 3 shows in a corresponding matrix of (2N+1)×(2M+1) sites the implementation of both grids: that associated to the pixel sites (=the circles) and that related to the contour sites (=the segments of lines). The contour elements that are situated between pixels of different labels are considered as active.
On turn, an element of the contour grid may have up to six active neighbours, as illustrated in FIG. 4, and, due to that, the contour grid is usually referred to as hexagonal grid. A way to code the partition information in the contour grid is to select an initial point in the grid and to track the active sites up to the end of the corresponding contour. This method performs a lossless coding of the partition information, by encoding the movement from a current contour element to the following neighbour contour element (only three possible movements: straight, right, left).
Another contour tracking method is to move through the contour using larger steps, only contour elements linked by such larger steps being encoded: in the above-cited document, the described MGCC technique uses basic cells of 3×3 pixels, as the one illustrated in FIG. 5, where all contour and pixel sites in the cell are shown. For compression efficiency reasons, two types of cells are then used: counter-clockwise, as in FIG. 6, or clockwise, as in FIG. 7. The way to index the different contour elements in each type of cell is presented: the initial contour site is denoted by the symbol 0 and the other ones by the symbols 1 to 7, the symbol 1 being assigned to the site which is on the same side of the cell as the symbol 0. Consequently, to characterize a cell, three parameters are necessary: its initial contour site, its type (clockwise or counter-clockwise), and its orientation (=east or west for a cell with an horizontal initial contour element, north or south for a vertical one). The coding algorithm selects between each of these two types of cell in order to maximize the number of contour elements coded per cell.
The MGCC technique uses said indexing as well as its possible rotations. Starting by the input element of the cell indexed with a 0 in FIG. 6, any output element from the set (1, 2, . . . , 6, 7) can be reached, but the way to go through the cell is not univocally defined by the output element: as shown in the example of FIGS. 8 and 9, a movement (in this case, from 0 to 4) may indeed correspond to two different contour configurations. The contour elements inside the cell (8, 9, 10, 11), not coded, introduce ambiguity in the coding process, two different sets of contour sites (0, 8, 9, 4 ) or (0, 11, 10, 4) being possible. This ambiguity introduces coding losses. Nevertheless the only possible error is the erroneous labeling of the central pixel of the cell, i.e. only of an isolated boundary pixel.
In a contour tracking process, several cells are then linked up in order to complete the contour. To link two cells, the output contour site of the current cell becomes the input contour site of the following cell, as FIG. 10 shows. When coding with the MGCC approach the boundary of a single region, the bitstream thus generated will therefore contain: (a) the position of the initial contour site, and (b) the chain of symbols representing the movements performed in order to track the contour.
In the contour tracking process, it is needed to change progressively the position of the basic cell through the grid. The proposed technique is described for instance in the article “Encoding of line drawings with a multiple grid chain code”, by T. Minami and K. Shinohara, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, no 2, March 1986, pp. 269–276. The basic principle is explained with reference to FIGS. 11 to 15.
As indicated in FIG. 11 giving an example of coding with a fixed grid, a contour segment has been here coded by means of the symbol 4 in the first cell (a counter-clockwise one). If cells of the same grid are used, the symbol 7 (FIG. 12) is used in the second cell for tracking the contour (the symbol 0 being always the new initial—or input—site), and the symbol 2 (FIG. 13) in the third one, these second and third cells being in that case clockwise ones. Three cells are therefore needed to track the contour from the first initial site. On the contrary, only two are needed if the grid (i.e., in fact, the position of the center of the cell) is changed: as shown in FIGS. 14 and 15 that illustrate a modification of the grid with respect to the example of FIGS. 11 to 13, only a second cell is now indeed needed to go to the same output site.
This solution of FIGS. 14 and 15 leads to a more compact representation of the contour. However, three different classes of grids are then necessary to define the shift of each grid with respect to the origin of the corresponding cell (called GO) before said shift. These three classes G1, G2, G3 are defined, as indicated in the following classification table, by the position (x, y) of the pixel which is the origin of each type of cell, with respect to the pixel which is the origin of said corresponding cell:
TABLE 1SHIFT WITH RESPECT TO THE ORIGINGRIDOF THE REFERENCE GRID GO:G0(0, 0)G1(1, 0)G2(0, 1)G3(1, 1)
In the example of FIG. 10, a cell of the class G2 was used (with respect to the corresponding current cell G0); in another example illustrated in FIG. 16, a cell of the class G1 is used (with respect to the corresponding current cell G0).
However, the MGCC approach previously described can only be used to code binary partitions. In case of general segmented pictures, the partitions contain regions that share contours, and said approach is no longer appropriate.